Integrated circuits are typically formed from many small building blocks which are typically termed cells. Efficient manufacture of the integrated circuit requires that the individual cells be designed so that, other factors being equal, surface area in minimized. Of course, the integrated circuit is formed from many cells and the cells, which need not have the same size, have to be arranged suitably with respect to each other. This arrangement has to be performed for memories, processors, application specific, digital signal processing, etc., integrated circuits.
Several techniques have been developed to assemble the individual cells. In one technique, the cells are stretched so that they pitch-match and are then assembled to form what is termed a tiled module. Although it would seem that this procedure uses space that could otherwise be usefully employed, it has been found that, especially for custom VLSI, the seemingly lost space is difficult to usefully employ. The cells must then be electrically connected to each other using the vertices, frequently termed ports, at the boundaries of the cells. There is no need for any knowledge of the internal structure of the cell for this step; only the port vertices need be known. However, for the cells to be stretchable, constraints between every pair of port vertices must be derived. The derived constraint set is called the closure constraints. A constraint refers to an inequality relation between two vertices (variables)v.sub.i +w.sub.ij .ltoreq.v.sub.j where w.sub.ij can be either positive or negative. If the cells have p ports, it has been found that the number of constraints is roughly proportional to p.sup.2. For cells with large number of ports, it becomes very difficult to satisfy all of the constraints in a reasonable time.
Accordingly, methods for reducing the number of constraints, i.e., the size of the closure constraint graph or set, have been sought. One method was reported by Reichelt, "An Improved Cell Model for Hierarchical Layout Compaction," MIT Master's thesis, 1987. This method relies on the realization that, for a given longest path, any subpath within the path is also a longest path. The problem of finding the longest path is functionally equivalent to the well known problem of finding the shortest path. Thus, if there is a longest path from x.sub.i to x.sub.j which goes through x.sub.k, the arc from x.sub.i to x.sub.j is redundant. This method, termed event cancellation, eliminates some redundant constraints, is advantageously employed in many situations. However, it has been found that it is ineffective in some situations, such as the situation in which there are multiple longest paths reaching a common vertex but having unequal numbers of edges. Our experience has been that these conditions constitute the majority of redundant constraints.